package com.sunny.l4;

public class Solution {

    public ListNode sortList(ListNode head) {

        if(null == head || null == head.next)
            return head;

        int len = getLen(head);

        ListNode p = head;

        NodeResult tmp = findMin(head);
        if(!tmp.isfirst){
            tmp.pre.next = tmp.node.next;
        }else{
            p = p.next;
        }
        head = tmp.node;
        ListNode ano = head;


        int cnt = 1;
        while (cnt ++ < len){
            tmp = findMin(p);
            if(!tmp.isfirst){
                tmp.pre.next = tmp.node.next;
            }else{
                p = p.next;
            }
            ano.next = tmp.node;
            ano = ano.next;
        }

        return head;
    }

    public int getLen(ListNode head){
        int res = 0;
        ListNode p = head;
        while (null != p){
            res++;
            p = p.next;
        }
        return res;
    }

    public NodeResult findMin(ListNode head){
        ListNode p = head;
        ListNode min = p;
        ListNode pre = null;
        ListNode resPre = null;
        while (null != p){
            if(p.val < min.val){
                resPre = pre;
                min = p;
            }
            pre = p;
            p = p.next;
        }
        boolean isFirst = false;
        if(min == head)
            isFirst = true;
        return new NodeResult(min, resPre, isFirst);
    }
}

class NodeResult{
    ListNode node;
    ListNode pre;
    boolean isfirst;

    public NodeResult(ListNode node, ListNode pre, boolean isfirst) {
        this.node = node;
        this.pre = pre;
        this.isfirst = isfirst;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
 }